HJ70 矩阵乘法计算量估算

本节目标：理解“HJ70 矩阵乘法计算量估算”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：40.49% 时间限制：1秒 空间限制：32M 知识点==字符串====栈== 描述 矩阵乘法的运算量与矩阵乘法的顺序强相关。 例如： A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵 计算ABC有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。 编写程序计算不同的计算顺序需要进行的乘法次数。 数据范围：矩阵个数： 1≤n≤15 ，行列数：1≤rowi,coli≤100 ，保证给出的字符串表示的计算顺序唯一。 进阶：时间复杂度：O(n) ，空间复杂度：O(n) 输入描述： 输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则 计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！ 输出描述： 输出需要进行的乘法次数 示例1 输入： 350 1010 2020 5(A(BC)) ==复制== 输出： 3500

这个问题是关于矩阵链乘法的优化问题，一个经典的动态规划问题。但是，根据输入的规则字符串来直接计算乘法次数的要求使得这个问题有点独特。我们可以使用栈来模拟计算过程，直接根据给定的顺序来计算乘法次数。

思路：

1. 首先，将每个矩阵的行列数读入并存储。
2. 然后，遍历计算法则字符串。每遇到一个左括号'('，我们预期会有一个矩阵乘法发生，直到遇到相应的右括号')'，这时我们计算这个特定乘法操作的乘法次数，并将结果"矩阵"的行列数压栈，以便用于后续的乘法计算。
3. 每次遇到矩阵（用字母表示）时，我们根据字母的顺序（'A'、'B'、'C'等）来获取其对应的行列数，并将其压栈。
4. 遇到右括号时，弹出栈顶的两个矩阵，计算它们的乘法次数，并将新的"矩阵"行列数压回栈中。

示例代码：

def matrix_multiply_cost(matrices, formula):

将矩阵信息存储在字典中，方便查找

matrix_dict = {chr(65+i): matrices[i] for i in range(len(matrices))} stack = [] # 使用栈来辅助计算 cost = 0 # 记录总的乘法次数 for char in formula: if char == ')':

遇到右括号，计算并合并栈顶的两个矩阵

m2 = stack.pop() m1 = stack.pop()

计算乘法次数：m1的行数 * m1的列数（即m2的行数） * m2的列数

current_cost = m1[0] * m1[1] * m2[1] cost += current_cost

将新的矩阵行列数压栈

stack.append((m1[0], m2[1])) elif char in matrix_dict:

遇到矩阵标识符，将其行列数压栈

stack.append(matrix_dict[char]) return cost

读取输入

n = int(input().strip()) # 矩阵个数 matrices = [] for _ in range(n): r, c = map(int, input().strip().split()) # 读取矩阵的行数和列数 matrices.append((r, c)) formula = input().strip() # 读取计算法则字符串

计算并输出乘法次数

print(matrix_multiply_cost(matrices, formula))

这个解法直接依据输入的计算顺序，通过模拟这个过程来计算乘法次数，避免了复杂的动态规划算法。需要注意的是，这种方法假设输入的计算顺序是合理的，即每次乘法操作都是可行的。